package com.wc.AlgoOJ_train.train1.c4.A410;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/9 15:37
 * @description RPG的错排
 * http://43.138.190.70:8888/p/A410
 */
public class Main {
    static BigInteger[] dp = new BigInteger[26];
    static BigInteger[] div = new BigInteger[26];
    static BigInteger[] ans = new BigInteger[26];

    public static void main(String[] args) {
        dp[0] = new BigInteger("1");
        dp[1] = new BigInteger("0");
        dp[2] = new BigInteger("1");
        div[0] = new BigInteger("1");
        div[1] = new BigInteger("1");
        div[2] = new BigInteger("2");
        for (int i = 3; i <= 25; i++) {
            dp[i] = (dp[i - 1].add(dp[i - 2])).multiply(new BigInteger(String.valueOf(i - 1)));
            div[i] = div[i - 1].multiply(new BigInteger(String.valueOf(i)));
        }
        ans[1] = new BigInteger("1");
        for (int i = 2; i <= 25; i++) {
            ans[i] = new BigInteger("0");
            int mid = (i + 1) / 2;
            // 把超过一半的加起来
            for (int j = mid; j <= i; j++) {
                ans[i] = ans[i].add(C(i, j).multiply(dp[i - j]));
            }
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n == 0) {
                return;
            }
            System.out.println(ans[n]);
        }
    }

    public static BigInteger C(int n, int m) {
        return div[n].divide(div[m].multiply(div[n - m]));
    }
}
